package java学习.代码随想录.动态规划.背包;

import 操作系统实验.实验二.生产者与消费者.Consumer;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/21 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 零钱兑换II {

    /**
     * 1. bagSize = 5
     * 纯完全背包是能否凑成总金额(背包重量的MaxValue)，而本题是要求凑成总金额的个数Number！
     * 故求方法数，求和
     * dp[j] 0~i个硬币数 凑成 amount 的最大个数
     *
     */
    public static int change(int amount, int[] coins) {


        int[] dp = new int[amount+1];
        dp[0] = 1;
//        for (int i = 1; i <=coins.length; i++) {
//            for (int j = coins[i-1]; j <=amount; j++) {
//                dp[j] +=dp[j-coins[i-1]];
//            }
//        }

        for (int i = 0; i <coins.length; i++) {
            for (int j = coins[i]; j <=amount; j++) {
                dp[j] +=dp[j-coins[i]];
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[amount];

    }

    public static int changeT(int amount, int[] coins) {


        int[][] dp = new int[coins.length+1][amount+1];
        for (int i = 0; i < coins.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i <coins.length; i++) {
            for (int j = coins[i]; j <=amount; j++) {
                dp[i][j] +=dp[i][j-coins[i]];
            }
        }
        for (int i = 0; i <coins.length; i++) {
            for (int j =0; j < amount; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
//        System.out.println(Arrays.toString(dp));
        return dp[coins.length][amount];

    }

    public static int changeT1(int cnt, int[] cs) {
        int n = cs.length;
        int[][] f = new int[n + 1][cnt + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int val = cs[i - 1];
            for (int j = 0; j <= cnt; j++) {
                f[i][j] = f[i - 1][j];
                for (int k = 1; k * val <= j; k++) {
                    f[i][j] += f[i - 1][j - k * val];
                }
            }
        }
        for (int i = 0; i <=cs.length; i++) {
            for (int j = 0 ; j <= cnt; j++) {
                System.out.print(f[i][j]+" ");

            }
            System.out.println();
        }
        return f[n][cnt];
    }

//    作者：AC_OIer
//    链接：https://leetcode.cn/problems/coin-change-2/solution/gong-shui-san-xie-xiang-jie-wan-quan-bei-6hxv/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    public static int changeReverse(int amount, int[] coins) {


        int[] dp = new int[amount+1];
        dp[0] = 1;
        for (int j = 0; j <=amount; j++) {
            for (int i = 1; i <=coins.length; i++) {
                if (j>=coins[i-1]){
                    dp[j] +=dp[j-coins[i-1]];
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[amount];

    }
    public static void main(String[] args) {
        int amount = 5;
        int[] coins = {1, 2, 5};
        System.out.println(changeT1(amount,coins));
        System.out.println("----------");
        System.out.println(change(amount,coins));
        System.out.println("----------");
        System.out.println(changeReverse(amount,coins));

    }


}
